G-systémy a dělitelnost

Popis: D:\binary\images\d_gdivi.jpg



Dělitelnost in G(n,k)

Číslo instance u(i,j) je soudělné s r=(n^k-1) právě když odpovídající číslo druhu g(i) je soudělné s r. Počet všech čísel, která nejsou soudělná s r je φ(r), kde φ je Eulerova funkce.

Jestliže g(i) není soudělné s r, pak jeho druh musí být vlastní (ne vnořený) a takový druh má k instancí.
Proto:

   φ(n^k-1) mod k = 0

E-druhy jsou druhy respektující:

   nsd(g,r)=1

kde nsd() označuje největší společný dělitel. Např. φ(2^4-1) = φ(15) = 8 (viz řádky označené hvězdičkou).

G(2,4)
  0
* 1  2  4  8
  3  6 12  9
  5 10
* 7 14 13 11
 15

Vidíme, že 8 mod 4 = 0.

G-koeficient g(n,k) = φ(n^k-1)/k

  n \ k |  1   2    3    4    5    6    7    8    9   10
  --------------------------------------------------------
    1   |  -   -    -    -    -   -    -     -    -    -
    2   |  1   1    2    2    6    6   18   16   48   60
    3   |  1   2    4    8   22   48  156  320 1008
    4   |  1   4   12   32  120  288 1512 4096
    5   |  2   4   20   48  280  720 5580
    6   |  4  12   56  216 1240
    7   |  2   8   36  160
    8   |  6  18  144
    9   |  4  16   96
   10   |  6  30
  n \ k | 11  12   13   14   15   16   17   18   19
 ----------------------------------------------------
    2   | 176 144 630  756 1800 2048 7710 7776 27594

Fermatova věta

Všechny třídy s gcd(g,r)=1, r=n^k-1 jsou vlastní třídy. System G(n,k) má n^k instancí. Jestliže p ε P, jen n instancí (instance z G(n,1)) je vnořených do systému G(n,p). Všechny ostatní třídy jsou vlastní třídy a mají k transposic. Proto p\(n^p-n), tj. n^p-n=0(mod p), tj. Fermatova věta. Fermatův koeficient f(n,k) = ((n^(k-1))-1)/k

      k\n|       2 |        3
      ------------------------
       3 |       1 |        1
       5 |       3 |       16
       7 |       9 |      104
      11 |      93 |     5368
      13 |     315 |    40880
      17 |    3855 |  2532160
      19 |   13797 |      ...
      23 |   182361|      ...

Instance dané třídy

Vyčísleme součet čísel instancí ve všech třídách G(3,3):

          0                0
          1   3   9       13
          2   6  18       26
          4  12  10       26
          5  15  19       39
          7  21  11       39
          8  24  20       52
         13               13
         14  16  22       52
         17  25  23       65
         26               26

Každý součet je dělitelný (n^k-1)/(n-1) = (3^3-1)/(3-1) = 13.

V G(n,k), platí pro každou třídu g(i):

     ∑ u(i,j) = 0  [ mod (n^k- 1)/(n-1)]
      j

Úroveň třídy

Nechť úroveň L(g) třídy g v G(n,k) je součet jednotlivých čísel (číslic) v jakékoliv instanci této třídy. Platí:

   L(g(i)) = ∑{j} u(i,j) / (c(k,q) * q/k)

kde q je počet transpozic (tj.řád výchozího vnořeného systému) a c(k,q) koeficient vnoření. Např. v G(3,3):

       g|      | L(g)  |k/q|  ∑ uij
      --+------+-------+---+------
       0| 000  |  0    | 3 |    0
       1| 001  |  1    | 1 |   13
       2| 002  |  2    | 1 |   26
       4| 011  |  2    | 1 |   26
       5| 012  |  3    | 1 |   39
       7| 021  |  3    | 1 |   39
       8| 022  |  4    | 1 |   52
      13| 111  |  3    | 3 |   13
      14| 112  |  4    | 1 |   52
      17| 122  |  5    | 1 |   65
      26| 222  |  6    | 3 |   26
    ...
        L(7) = 3/3* 39/c(3,1) = 1*39/ ((3^3-1)/(3-1)) = 39/13 =3
        L(8) = 3/3* 52/c(3,1) = 1*52/ ((3^3-1)/(3-1)) = 52/13 =4
        ...
        L(13)= 3/1* 13/c(3,1) = 3*13/ ((3^3-1)/(3-1)) = 39/13 =3
        ...

Schematická algebra